package BinarySearchTree;
/**      二叉搜索树的概念:
        它或者是一棵空树，或者是具有下列性质的二叉树：
        1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
        2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
        3. 它的左、右子树也分别为二叉排序树。
        因此，若对它进行中序遍历，则是一颗递增的排好序的序列！ 这一点很重要！
    插入和删除的时间复杂度:O(Logn)  最坏单分支:O(N)
 */
public class BinarySearchTree {
    public TreeNode root;

    //查找二叉搜索树指定的val值
    public TreeNode refind(int val) {
        //1.递归
        if (root.val < val) {
            root = root.right;
        } else if (root.val > val) {
            root = root.left;
        } else {
            return root;
        }
        TreeNode result = refind(val);
        if (result != null) {
            return result;
        }
        return null;
    }

    public TreeNode find(int val) {
        //2.非递归
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }

    //插入一个数据(都插入到了叶子结点)
    public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode parent = null;      //存放前一个结点
        TreeNode cur = root;
        TreeNode node = new TreeNode(val);
        while (cur != null) {
            if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val == val) {       //在一棵二叉搜索树中，一般不会插入一个相同的值
                return;
            } else {      //表示应该在root的右边插入
                parent = cur;
                cur = cur.right;
            }
        }
        if (parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    /**删除值为val的结点  （使用替换思想）
     *  四种情况:1.删除结点的左边为空
     *         2.删除结点的右边为空
     *         3.删除结点的两边都不为空
     *         4.删除结点的两边都为空
     */
    public void remove(int val) {
        //首先先找到这个需要删除的结点和他的父节点（即前一个结点）
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                removeNode(parent,cur);        //删除完这个结点就结束
                return;
            }
        }
    }

    /**   1.删除结点的一边为空
     *        cur.left == null
     *           1.cur为根   2.cur在parent节点的左边   3.cur在parent结点的右边
     *      cur:   12               12                     12
     *               15     cur: 10   15                10  cur： 15
     *            14   20         11 14  20                        13
     *
     *        cur.right == null
     *           1.cur为根    2.cur在parent节点的左边   3.cur在parent结点的右边
     *      cur:  12             12                        12
     *          10       cur: 10    15                  10   cur：15
     *         8  9         8     14  20                        14
     *     2.删除结点两边都不为空
     *         cur.left != null && cur.right != null
     *             80                                    80
     *       30   cur： 100                         30   cur： 100
     *     20  50    90  110                      20  50    90   110
     *                107                                           115
     */
    private void removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            }else if(cur == parent.right) {
                parent.right = cur.right;
            }else {
                parent.left = cur.right;
            }
        }
        if(cur.right == null) {
            if(cur == root) {
                root = root.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }
//        if(cur.left == null && cur.right == null) {       //这边可以不写因为两个都为空的时候，上面肯定会满足，直接把这个结点删除
//            if(cur == root) {
//                root = null;
//            }else if(cur == parent.left) {
//                parent.left = null;
//            }else {
//                parent.left = null;
//            }
//        }
        if(cur.left != null && cur.right != null) {
            //思想；找一个右边最小的数替换这个需要删除的数值，再把右边最小的数的结点删除
            TreeNode replaceparent = cur;
            TreeNode replace = cur.right;
            //一定要找到 replace.left 为空的情况，这样子的replace这个结点才是cur右边最小的
            while(replace.left != null) {
                replaceparent = replace;
                replace = replace.left;
            }
            /** 到了这里replace左边一定为空，否则replace就不会是最小
             *        25                                                    25
             *    15     cur:35                                        15     cur: 35
             *            30    40                                             30      40  replace
             *        replace:38   45                                                     45
             *                  39
             *
             */
            cur.val = replace.val;
            //如果replace的左边存在比cur大，但是整体满足是一棵搜索二叉树，就可以找那个最小值替换
            if(replaceparent.left == replace) {
                replaceparent.left = replace.right;         //如果replace右边有结点，就把他右边连接上，如果没有就直接是null
            }else {
              //如果没找到，那么最小值就是replace
                replaceparent.right = replace.right;
            }
        }
    }

    public void creatTree() {
        TreeNode A = new TreeNode(50);
        TreeNode B = new TreeNode(3);
        TreeNode C = new TreeNode(80);
        TreeNode D = new TreeNode(1);
        TreeNode E = new TreeNode(4);
        TreeNode F = new TreeNode(60);
        TreeNode G = new TreeNode(100);
        TreeNode H = new TreeNode(0);
        TreeNode I = new TreeNode(2);
        TreeNode j = new TreeNode(120);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        D.right = I;
        G.right = j;
        root = A;
    }

    public void inOrder(TreeNode root) {       //前序遍历
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}
